package no95;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/5/20 0:20
 * II 最长公共子序列
 * https://leetcode.cn/problems/qJnOS7/
 */
public class Solution01 {

    public int longestCommonSubsequence(String text1, String text2) {
        // 定义 dp[i][j] 表示在 text1 的第 i 个位置与 text2 的第 j 个位置结尾的最长公共子序列的长度
        int[][] dp = new int[text1.length()+1][text2.length()+1];
        int i = 1; int j = 1; // 用于迭代 dp 状态量
        for(char c1 : text1.toCharArray()) {
            for(char c2 : text2.toCharArray()) {
                if(c1 == c2) {
                    dp[i][j] = dp[i-1][j-1] + 1;
                } else{
                    dp[i][j] = Math.max(dp[i-1][j], dp[i][j-1]);
                }
                ++j;
            }
            ++i;
            j = 1; // 回退
        }
        return dp[text1.length()][text2.length()];
    }
}
